Leetcode-20:Valid Parentheses

2018-01-02

问题描述：

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

我的答案

//括号匹配，堆栈
bool isValid(string s) {
    stack<char> string;
    for(int i = 0;i<s.length();i++){
        switch (s[i]) {
            case '(':
                string.push('(');
                break;
            case '[':
                string.push('[');
                break;
            case '{':
                string.push('{');
                break;
            case ')':
                if(string.empty()){
                    return false;
                }else{
                    if(string.top() != '('){
                        return false;
                    }else{
                        string.pop();
                    }
                }
                break;
            case ']':
                if(string.empty()){
                    return false;
                }else{
                    if(string.top() != '['){
                        return false;
                    }else{
                        string.pop();
                    }
                }
                break;
            case '}':
                if(string.empty()){
                    return false;
                }else{
                    if(string.top() != '{'){
                        return false;
                    }else{
                        string.pop();
                    }
                }
                break;
            default:
                break;
        }
    }
    if(string.empty()){
        return true;
    }else{
        return false;
    }
}

其他高效答案

bool isValid(string s) {
        std::stack<char> my_stack;
        for (int i = 0; i < s.length(); i++) {
            if (isOpening(s[i]))
                my_stack.push(s[i]);
            else if (isClosing(s[i]) && !my_stack.empty()) {
                if (s[i] == '}' && my_stack.top() != '{')
                    return false;
                else if (s[i] == ')' && my_stack.top() != '(')
                    return false;
                else if (s[i] == ']' && my_stack.top() != '[')
                    return false;
                else
                    my_stack.pop();
                
            } else
                return false;
        }
        if (my_stack.empty())
            return true;
        return false;  
        
    }